package com.study.test;

/**
 * 基数排序
 *
 * @Author hupengming
 * @ClassName RadixSort
 * @Date 2023-06-02  15:58
 * @Version 1.0
 */
public class CodeRadixSort {

    public static void main(String[] args) {

//        int[] arr = new int[]{2, 5, 4, 1, 7, 3, 8, 2};
//        radixSort(arr);
//
//        for (int i : arr) {
//            System.out.print(i);
//        }

//        yangHui(5);
//
//        int[] fbnq = fbnq(9);
//        for (int i : fbnq) {
//            System.out.print(i+ " ");
//        }

        long aa = 1686196263339L;
        long bb = 1686196263341L;

        System.out.println(aa > bb);





    }

    /**
     * 斐波那契数列，也称兔子数列：1,1,2,3,5,8,13,21,34.....
     * 解析:第一项为1，第二项为1，从三项开始数值是前两项之和
     */
    public static int[] fbnq(int n){

        int[] arr = new int[n];

        for (int i = 0; i < n; i++) {
            if(i < 2){
                arr[i] = 1;
            }else {
                arr[i] = arr[i - 1] + arr[i - 2];
            }
        }
        return arr;
    }


    /**
     * 杨辉三角
     *
     *          * 1
     *          * 1 1
     *          * 1 2 1
     *          * 1 3 3 1
     *          * 1 4 6 4 1
     *
     */
    public static void yangHui(int n){

        int[][] arr = new int[n][n];

        for (int i = 0; i < arr.length; i++) {
            arr[i][0] = 1;
            arr[i][i] = 1;

            for (int j = 1; j < i; j++) {
                arr[i][j] = arr[i-1][j] + arr[i-1][j-1];
            }
        }

        for (int i = 0; i < arr.length; i++) {

            for (int k = 0; k <= i; k++) {

                System.out.print(arr[i][k]);
            }

            System.out.println();
        }
    }


    public static void radixSort(int[] arr) {

        if (arr == null || arr.length < 2) {
            return;
        }
        radixSort(arr, 0, arr.length - 1, maxBits(arr));
    }

    /**
     * 基数排序
     *
     * @param arr   数组
     * @param L     开始位置
     * @param R     结束位置
     * @param digit 数组最大位置有几位
     */
    public static void radixSort(int[] arr, int L, int R, int digit) {
        final int radix = 10;
        int i = 0, j = 0;

        int[] bucket = new int[R - L + 1];

        for (int k = 1; k <= digit; k++) { // digit多大表示进出多少次。 意思表示出桶进桶多少次。个位->十位->百位
            // 辅助空间，替换桶空间
            int[] count = new int[radix];

            for (i = L; i <= R; i++) { // 数组排序的范围
                j = getDigit(arr[i], k); // 获取数组下标为l上的数字的第k位置的数
                count[j]++; //把count数组下标是第n位上的数字自增
            }

            // count数组累加前一项的和
            for (i = 1; i < radix; i++) {
                count[i] = count[i] + count[i - 1];
            }

            // 表示出桶
            for (i = R; i >= L; i--) {
                j = getDigit(arr[i], k);
                bucket[count[j] - 1] = arr[i];
                count[j]--;
            }

            for (i = L, j = 0; i <= R; i++, j++) {
                arr[i] = bucket[j];
            }
        }
    }


    /**
     * 获取这个数字的第几位
     *
     * @param num 一个源数字
     * @param k   表示获取源数字的第几位
     * @return
     */
    public static int getDigit(int num, int k) {
        return ((num / ((int) Math.pow(10, k - 1))) % 10);
    }

    /**
     * 数组中最大的数有几位
     *
     * @param arr
     * @return
     */
    public static int maxBits(int[] arr) {

        int max = Integer.MIN_VALUE;

        for (int i = 0; i < arr.length; i++) {

            max = Math.max(arr[i], max);

        }
        int res = 0; // 多大是表示数组中最大的数有几位

        while (max != 0) {
            res++;
            max /= 10;
        }
        return res;
    }

}
